#include <iostream>
#include "sort.h"
using namespace std;
/******************************************************************************
func:printf the first n elements of the array;
inpt:*@arr is a pointer that points at the first address of the array;
	 *@n is the length that will be sorted usually equals the length of the array;
oupu:
note:
date:03/21/2021 by xiyin,li in hust;
******************************************************************************/
void printArray(int* arr, size_t n) {
	for (unsigned int ii = 0; ii < n; ii++) {
		cout << *(arr + ii) << "	";
	}
	cout << endl;
}
/******************************************************************************
func:
inpt:*@arr is a pointer that points at the first address of the array;
	 *@n is the length that will be sorted usually equals the length of the array;
oupu:
note:time complexity:O(n^2);space complexity:O(1);
date:03/21/2021 by xiyin,li in hust;
******************************************************************************/
void bubbleSort(int* arr, size_t n) {
	int temp;
	for (unsigned int ii = 0; ii < n - 1; ii++) {
		for (unsigned int jj = 0; jj < n - 1 - ii; jj++) {
			if (*(arr + jj) > *(arr + jj + 1)) {
				temp = *(arr + jj);
				*(arr + jj) = *(arr + jj + 1);
				*(arr + jj + 1) = temp;
			}
		}
	}
}
/******************************************************************************
func:
inpt:*@arr is a pointer that points at the first address of the array;
	 *@n is the length that will be sorted usually equals the length of the array;
oupu:
note:time complexity O(n^2);sapce complexity O(1);
date:03/22/2021 by xiyin,li in hust;
******************************************************************************/
void selectSort(int* arr, size_t n) {
	int minValueIndex;
	int temp;
	for (unsigned int ii = 0; ii < n-1; ii++) {
		minValueIndex = ii;
		for (unsigned jj = ii + 1; jj < n; jj++) {
			if (*(arr + jj) < *(arr + minValueIndex)) {
				minValueIndex = jj;
			}
		}
		temp = *(arr + minValueIndex);
		*(arr + minValueIndex) = *(arr + ii);
		*(arr + ii) = temp;
	}
}

/******************************************************************************
func:
inpt:*@arr is a pointer that points at the first address of the array;
	 *@n is the length that will be sorted usually equals the length of the array;
oupu:
note:
date:03/23/2021 by xiyin,li in hust;
******************************************************************************/
void insertSort(int* arr, size_t n) {
	int curValue;
	for (unsigned int ii = 1; ii < n; ii++) {
		curValue = *(arr + ii);
		int jj = ii - 1;
		while (jj >= 0 && *(arr+jj)>curValue) {
			*(arr + jj + 1) = *(arr + jj);
			jj--;
		}
		*(arr + jj + 1) = curValue;
	}
}
/******************************************************************************
func:
inpt:*arr is a pointer that points at the first address of the array;
	 *n is the length that will be sorted usually equals the length of the array;
oupu:
note:
date:03/23/2021 by xiyin,li in hust;
******************************************************************************/
void  shellSort(int* arr, size_t n) {
	int gap = n / 2;
	for (int gap = n / 2; gap > 0; gap = gap / 2) {
		for (int ii = gap; ii < n; ii++) {
			int curValue = *(arr + ii);
			int jj = ii;
			while (jj > 0 && *(arr + jj - gap) > curValue) {
				*(arr + jj) = *(arr + jj - gap);
				jj = jj - gap;
			}
			*(arr + jj) = curValue;
		}
	}
}
/******************************************************************************
func:
inpt:*arr is a pointer that points at the first address of the array;
	 *n is the length that will be sorted usually equals the length of the array;oupu:
oupt:
note:it's DIFFICULT for me now!
date:03/24/2021 by xiyin,li in hust;
******************************************************************************/
void mergeSort(int* arr, size_t n) {
	;
}
void merge(int* arr, int low, int mid, int high) {
	int i = low;
	int j = mid + 1;
	int k = 0;
	int n = high - low + 1;
	int *tmp = new int[n];
	while (i <= mid && j <= high) {
		tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j]++;
	}
	while (i <= mid) {
		tmp[k++] = arr[i++];
	}
	while (j <= high) {
		tmp[k++] = arr[j++];
	}
	for (int ii = 0; ii < n; ii++) {
		arr[low + ii] = tmp[ii];
	}
	delete []tmp;
}
/******************************************************************************
func:Quick Sort
inpt:*arr is a pointer that points at the first address of the array;
	 *n is the length that will be sorted usually equals the length of the array;oupu:
oupt:
note:it's DIFFICULT for me now!
date:03/24/2021 by xiyin,li in hust;
******************************************************************************/
void quickSort(vector<int>& nums, int l, int r) {
	if (l + 1 >= r) { return; }
	int first = 1; 
	int last = r - 1;
	int key = nums[first];
	while (first < last) {

	}
}